﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class ToolsetForArrayOfInteger :Interface
    {
        int gItem;
        int[] gArray;
        static Random r = new Random();

        public void sort(ref int[] array)
        {
            QuicksortRecursive(ref array);
        }
        private void QuicksortRecursive(ref int[] array)
        {
            SortBetween(ref array, 0, array.Length - 1);
        }
        private void SortBetween(ref int[] gQArray, int iLow, int iHigh)
        {
            int iLeft;
            int iRight;
            int separator;
            int temp;
            iLeft = iLow;
            iRight = iHigh;
            separator = gQArray[((iLow + iHigh) / 2)]; //auch random verwendet
            do
            {
                while (gQArray[iLeft] < separator) { iLeft++; }
                while (separator < gQArray[iRight]) { iRight--; }
                if (iLeft <= iRight)
                {
                    temp = gQArray[iLeft];
                    gQArray[iLeft] = gQArray[iRight];
                    gQArray[iRight] = temp;
                    iLeft++;
                    iRight--;
                }

            } while (iRight > iLeft);
            if (iLow < iRight) { SortBetween(ref gQArray, iLow, iRight); };
            if (iLeft < iHigh) { SortBetween(ref gQArray, iLeft, iHigh); };
        }

        public bool sorted(int[] array)
        {
            return SortedBetween(array, 0, array.Length - 1);
        }
        private bool SortedBetween(int[] array, int left, int right)
        {
            while ((left < right) && (array[left] <= array[left + 1]))
            {
                left++;
            }
            return left >= right;
        }
        private bool SortedBetweenRecursive(int[] array, int left, int right)
        {
            return (left >= right) | ((array[left] <= array[left + 1]) & SortedBetweenRecursive(array, left + 1, right));
        }

        public bool has(int[] array, int item)
        {
            gArray = array;
            gItem = item;
            return HasBetween(0, array.Length - 1);
        }
        private bool HasBetween(int left, int right)
        {
            int mid;
            if (left > right)
            {
                return false;
            }
            else
            {
                mid = (left + right) / 2;
                if (gItem < gArray[mid])
                {
                    return HasBetween(left, mid - 1);
                }

                if (gItem > gArray[mid])
                {
                    return HasBetween(mid + 1, right);
                }
                else return true;
            }
        }
        private bool HasIterative(int[] array, int i)
        {
            int left = 0;
            int right = (array.Length - 1);
            int mid = (array.Length / 2);
            while ((left <= right) & (i != array[mid]))
            {
                if (i < array[mid])
                {
                    right = mid - 1;
                }
                else
                { left = mid + 1; }
                mid = ((left + right) / 2);
            }

            return left <= right;
        }

        public void DetermineRangeWithMaxSum(int[] array, ref int maxHigh, ref int maxLow, ref int maxSum)
        {
            int low;
            int high;
            int sum;
            low = 0;
            sum = array[low];
            maxLow = low;
            maxHigh = low;
            maxSum = sum;
            for (high = low + 1; high == array.Length - 1; high++)
            {
                if (sum == 0) { low = high; sum = 0; }
                array[high] += sum;
                if (sum > maxSum) { maxLow = low; maxHigh = high; maxSum = sum; }
            }

        }

        public int[] InitRandom(int maxElement)
        {
           
            int[] array = new int[maxElement];
            for (int index = 0; index < array.Length; index++)
            {
                array[index] = r.Next(-maxElement, maxElement);
            }
            
         
            return array;
        }
    }

    }

